package com.mdnote.algorithm;

import java.awt.*;
import java.util.*;
import java.util.List;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/8
 * @description 贪心算法
 */
public class GreedyAlgorithm {

    public static void main(String[] args) {
        GreedyAlgorithm greedyAlgorithm = new GreedyAlgorithm();

        HashMap<String, HashSet<String>> allOptions = new HashMap<>();

        HashSet<String> option1 = new HashSet<>();
        option1.add("广州");
        option1.add("北京");
        option1.add("深圳");

        HashSet<String> option2 = new HashSet<>();
        option2.add("广州");
        option2.add("北京");
        option2.add("长沙");

        HashSet<String> option3 = new HashSet<>();
        option3.add("大连");
        option3.add("贵州");
        option3.add("长沙");

        HashSet<String> option4 = new HashSet<>();
        option4.add("广州");
        option4.add("贵州");

        allOptions.put("Channel 1", option1);
        allOptions.put("Channel 2", option2);
        allOptions.put("Channel 3", option3);
        allOptions.put("Channel 4", option4);

        HashSet<String> allCitySet = new HashSet<>();
        allOptions.forEach((key, value) -> {
            allCitySet.addAll(value);
        });

        allCitySet.forEach(s -> System.out.println(s));
        List<String> selectList = greedyAlgorithm.select(allOptions, allCitySet);

        System.out.println(selectList);
    }

    private List<String> select(Map<String, HashSet<String>> alloptionsMap, Set<String> allCitySet) {

        List<String> selectList = new ArrayList<>();
        // 临时集合
        Set<String> tempSet = new HashSet<>();
        while (!allCitySet.isEmpty()) {
            // 定义一个maxKey指向覆盖最大的那个元素
            String maxKey = null;
            tempSet.clear();
            for (Map.Entry<String, HashSet<String>> entry : alloptionsMap.entrySet()) {
                // 保存当前的value到临时集合
                tempSet.addAll(entry.getValue());
                // 得到交集
                tempSet.retainAll(allCitySet);

                // 找到覆盖率最大的key
                if (tempSet.size() > 0 && (maxKey == null || tempSet.size() > alloptionsMap.get(maxKey).size())) {
                    maxKey = entry.getKey();
                }
            }
            // 找到最大值
            if (maxKey != null) {
                // 把覆盖的城市删掉
                allCitySet.removeAll(alloptionsMap.get(maxKey));
                // =添加到集合中
                selectList.add(maxKey);
            }
        }

        return selectList;
    }
}
